﻿#pragma once
#include<assert.h>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<string>
#include<climits>
#include<functional>
#include"UnionFindSet.h"
using std::greater;
using std::priority_queue;
using std::string;
using std::vector;
using std::queue;
using std::map;
using std::set;
using std::cout;
using std::endl;

//邻接矩阵
//优点：
//1.适合存稠密图
//2.判断两个顶点是否有边，边的权值的时间复杂度是O(1)
//缺点：
//1.不适合存稀疏图
//2.不适合查找一个顶点连接的所有边。时间复杂度：O(N)

//邻接表
//优点：
//1.适合存储稀疏图
//2.查找一个顶点连接的所有边是O(1)
//缺点：
//1.不适合存储稠密图
//2.不适合确定两个顶点之间边的权值，是否相连，时间复 杂度O(1 )

//邻接矩阵 存储 图
namespace matrix
{
	//       vertex   weight                           默认无向图
	template<class V, class W=int, W MAX_W = INT_MAX, bool Direction=false>
	class graph
	{
		typedef graph<V, W, MAX_W, Direction> Self;
	public:
		//graph() = default;
		graph(){};
		graph(const V* a,size_t n):_vertexs(n),_edges(n,vector<W>(n,MAX_W))
		{
			for (size_t i = 0; i < n; i++)
			{
				_vertexs[i] = a[i];
				_indexMap[a[i]] = i;
			}
		}
		void addEdge(const V& src, const V& dst, const W& w)
		{
			int index1 = getVertexIndex(src);
			int index2 = getVertexIndex(dst);
		
			_edges[index1][index2] = w;

			if (Direction == false)
				_edges[index2][index1] = w;
		}
		void _addEdge(size_t srci,size_t dsti,const W& w)
		{
			_edges[srci][dsti] = w;

			if (Direction == false)
				_edges[dsti][srci] = w;
		}

		void print()
		{
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				cout << "[" << i << "] ->" << _vertexs[i] << endl;
			}
			cout << " ";
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				printf("%4d",i);
			}
			cout << endl;

			for (size_t i = 0; i < _edges.size(); i++)
			{
				cout << i;

				for (size_t j = 0; j < _edges.size(); j++)
				{
					if (_edges[i][j] == MAX_W)
					{
						printf("%4c",'*');
					}
					else
					{
						printf("%4d", _edges[i][j]);
					}
				}
				cout << endl;
			}

		}

		//广度优先遍历
		void BFS(const V& v)
		{
			cout << "BFS: ";
			int index = getVertexIndex(v);
			queue<int> q;
			set<int> s;
			int size;
			q.push(index);
			s.insert(index);
			while (!q.empty())
			{
				size = q.size();
				while (size--)
				{
					int index = q.front();
					q.pop();
					cout << index << ""<<_vertexs[index]<<" ";
					for (size_t i = 0; i < _edges[index].size(); i++)
					{
						if (_edges[index][i] != MAX_W && s.find(i) == s.end())
						{
							s.insert(i);
							q.push(i);
						}
					}
				}
				cout << endl;
			}
		}

		//深度优先遍历
		void DFS(const V& v)
		{
			cout << "DFS : ";
			vector<bool> visited(_vertexs.size(), false);
			int index = getVertexIndex(v);
			cout << index << ":" << _vertexs[index] << endl;
			visited[index] = true;
			_DFS(index, visited);
		}
		void _DFS(size_t srci,vector<bool>& visited)
		{
			for (int i = 0; i < _edges[srci].size(); i++)
			{
				if (_edges[srci][i] != MAX_W && visited[i] == false)
				{
					cout << i << ":" << _vertexs[i] << endl;
					visited[i] = true;
					_DFS(i,visited);
				}
			}
		}

		//最小生成树算法
		//最小生成树：构成生成树这些边，加起来权值最小
		//生成树==最小连通图
		//连通图：任意两个顶点之间都有路径
		//最小连通图：最少边的连通图。如果顶点有n个，则最少路径为n-1

		//Kruskal算法 本质贪心算法
		//大致过程：每次选最小边（当然选择的这条边不能构成环路)
		//返回值：如果选不出最小生成树返回权值最大值（因为可能图本身就不是连通图）
		//       如果选出返回最小生成树路径总和
		W Kruskal(Self& minTree) 
		{
			cout << "Kruskal:开始选边" << endl;

			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._edges.resize(_vertexs.size());
			for (auto& e : minTree._edges)
				e.resize(_vertexs.size(), MAX_W);

			priority_queue<Edge, vector<Edge>, greater<Edge>> minEdge;
			size_t n = _edges.size();
			for(size_t i = 0; i < n; i++)
				for (size_t j = i + 1; j < n; j++)
				{
					if (_edges[i][j] != MAX_W)
						minEdge.push(Edge(i, j, _edges[i][j]));
				}

			int size = 0;
			W total_w = W();
			UnionFindSet ufs(n);
			while (!minEdge.empty())
			{
				Edge min = minEdge.top();
				minEdge.pop();
				if (!ufs.InSameSet(min._srci, min._dsti))
				{
					cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << endl;
					minTree._addEdge(min._srci, min._dsti, min._w);
					ufs.Union(min._srci, min._dsti);
					size++;
					total_w += min._w;
				}
			}

			if (size == n - 1)
				return total_w;
			else
				return MAX_W;
		}

		//局部贪心
		W Prim(Self& minTree, const V& v)
		{
			cout << "Prim:开始选边" << endl;
			size_t n = _vertexs.size();
			minTree._vertexs = _vertexs;
			minTree._indexMap = _indexMap;
			minTree._edges.resize(n);
			for (auto& e : minTree._edges)
				e.resize(n, MAX_W);

			size_t srci = getVertexIndex(v);
			set<size_t> X;
			set<size_t> Y;
			X.insert(srci);
			for (size_t i = 0; i < n; i++) 
			{
				if (i != srci)
					Y.insert(i);
			}

			priority_queue<Edge, vector<Edge>, greater<Edge>> minEdges;
			for (int i = 0; i < n; i++)
			{
				if (_edges[srci][i] != MAX_W)
					minEdges.push(Edge(srci, i, _edges[srci][i]));
			}

			auto IsInSet = [](const set<size_t>& X, size_t index)
			{
				return X.find(index) != X.end();
			};


			size_t count = 0;
			W total_w = W();
			//从X与Y集合中连接的边里面选出最小边
			while (!minEdges.empty())
			{
				Edge e = minEdges.top();
				minEdges.pop();
				if (!IsInSet(X, e._dsti))
				{
					X.insert(e._dsti);
					Y.erase(e._dsti);
					minTree._addEdge(e._srci, e._dsti, e._w);
					cout << _vertexs[e._srci] << "->" << _vertexs[e._dsti] << endl;
					count++;
					total_w += e._w;

					if (count == n - 1) break;

					for (int i = 0; i < n; i++)
					{
						if (_edges[e._dsti][i] != MAX_W && !IsInSet(X,i))
							minEdges.push(Edge(e._dsti, i, _edges[e._dsti][i]));
					}

				}
			}
			if (count == n - 1)
				return total_w;
			else
				return MAX_W;

		}

		//单源最短路径
		//空间复杂度O(N²)
		void Dijkstra(const V& src,vector<W>& minDis,vector<size_t>& minPath)
		{
			size_t srci = getVertexIndex(src);
			size_t n = _vertexs.size();
			minDis.resize(n, MAX_W);
			minPath.resize(n, UINT_MAX);
			minDis[srci] = W();

			vector<bool> Y(n, true);
			//获取Y集合中最小值的点下标
			auto getYminVertex = [n,&minDis](const vector<bool>& Y)
			{
				size_t minIndex = UINT_MAX;
				for (size_t i = 0; i < n; i++)
				{
					if (Y[i] == true)
					{
						if (minIndex == UINT_MAX)
							minIndex = i;
						else
							minDis[i] < minDis[minIndex] ? minIndex = i : 1;
					}

				}
				return minIndex;
			};

			int minValueIndex;
			while ((minValueIndex = getYminVertex(Y)) != UINT_MAX)
			{
				Y[minValueIndex] = false;
				//松弛
				for (size_t i = 0; i < n; i++)
				{
					if (_edges[minValueIndex][i] != MAX_W)
						if (minDis[minValueIndex] + _edges[minValueIndex][i] < minDis[i])
						{
							minDis[i] = minDis[minValueIndex] + _edges[minValueIndex][i];
							minPath[i] = minValueIndex;
						}
				}
			}
		}

		//单源最短路径
		//时间复杂度O(N*E) 顶点数*边数
		void Bellman_ford(const V& src,vector<W>& minDis,vector<size_t>& minPath)
		{
			size_t n = _vertexs.size();
			size_t srci = getVertexIndex(src);
			minDis.resize(n, MAX_W);
			minPath(n, UINT_MAX);
			minDis[srci] = W();
		}
		 
		void PrinrtShotPath(const V& src, vector<W>& minDis, vector<size_t>& minPath)
		{
			size_t srci = getVertexIndex(src);
			cout << "[" << srci << "]" << ":" << _vertexs[srci] << "起点" << endl;
			cout << "最短路径距离" << endl;
			for (size_t i = 0; i < minDis.size(); i++)
			{
				cout << "[" << i << "]:" << _vertexs[i] << "-" << minDis[i] << endl;
			}
			cout << "最短路径" << endl;
			for (size_t i = 0; i < minPath.size(); i++)
			{
				cout << "[" << i << "]:" << _vertexs[i] << "-" << minPath[i] << endl;
			}
		}
		bool BellmanFord(const V& src, vector<W>& minDis, vector<size_t>& minPath)
		{
			size_t n = _vertexs.size();
			size_t srci = getVertexIndex(src);
			minDis.resize(n, MAX_W);
			minPath.resize(n, UINT_MAX);
			minDis[srci] = 0;

			vector<bool> IsInQue(n, false);

			queue<size_t> Vertexs;
			Vertexs.push(srci);
			IsInQue[srci] = true;

			vector<size_t> wayOfV(n, 0);
			wayOfV[srci] = 1;

			while (!Vertexs.empty())
			{
				size_t v = Vertexs.front();
				Vertexs.pop();
				IsInQue[v] = false;

				//松弛操作
				for (int i = 0; i < n; i++)
				{
					if (i != v && _edges[v][i] != MAX_W && minDis[v] + _edges[v][i] < minDis[i])
					{
						minDis[i] = minDis[v] + _edges[v][i];
						minPath[i] = v;
						wayOfV[i] = wayOfV[v] + 1;
						if (wayOfV[i] > n)
							return false;
						if (IsInQue[i] == false)
						{
							Vertexs.push(i);
							IsInQue[i] = true;
						}
					}
				}
			}

			return true;
		}
		//多源最短路径
		void Floyd_Warshall()
		{

		}

	private:
		
		struct Edge
		{
			size_t  _srci;
			size_t  _dsti;
			W _w; 
			Edge(size_t srci,size_t dsti,W w):_srci(srci),_dsti(dsti),_w(w)
			{}
			bool operator>(const Edge& e) const 
			{
				return _w > e._w;
			}
		};
		int getVertexIndex(const V& v)
		{
			auto ret = _indexMap.find(v);
			if (ret == _indexMap.end())
				assert(false);
			else
				return ret->second;
		}
	private:
		vector<V> _vertexs;   //下标映射顶点
		map<V, int> _indexMap;//顶点映射下标 
		vector<vector<W>> _edges;
	};


	void test_1()
	{
		string a[] = { "张三","李四","王五","赵六","周七" };

		graph<string, int, INT_MAX> g(a, sizeof(a) / sizeof(string));
		g.addEdge("张三", "李四", 100);
		g.addEdge("张三", "王五", 200);
		g.addEdge("王五", "赵六", 30);
		g.addEdge("王五", "周七", 30);

		g.print();
		cout << endl;
		g.BFS("张三");
		cout << endl;
		g.DFS("张三");
	}
	//测试最小生成树
	void TestGraphMinTree()
	{
		const char str[] = "abcdefghi";
		graph<char, int> g(str, strlen(str));
		g.addEdge('a', 'b', 4);
		g.addEdge('a', 'h', 8);
		//g.addEdge('a', 'h', 9);
		g.addEdge('b', 'c', 8);
		g.addEdge('b', 'h', 11);
		g.addEdge('c', 'i', 2);
		g.addEdge('c', 'f', 4);
		g.addEdge('c', 'd', 7);
		g.addEdge('d', 'f', 14);
		g.addEdge('d', 'e', 9);
		g.addEdge('e', 'f', 10);
		g.addEdge('f', 'g', 2);
		g.addEdge('g', 'h', 1);
		g.addEdge('g', 'i', 6);
		g.addEdge('h', 'i', 7);
		graph<char, int> kminTree;

		cout << "Kruskal:" << g.Kruskal(kminTree) << endl;
		kminTree.print();
		graph<char, int> pminTree;
		/*for(auto e : str)
		cout << "Prim:" << g.Prim(pminTree, str) << endl;*/
		for (int i=0;i<strlen(str);i++)
			cout << "Prim:" << g.Prim(pminTree, str[i]) << endl;
		pminTree.print();
	}
	//测试TestGraphDijkstra
	void TestGraphDijkstra()
	{
		const char* str = "syztx";
		graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.addEdge('s', 't', 10);
		g.addEdge('s', 'y', 5);
		g.addEdge('y', 't', 3);
		g.addEdge('y', 'x', 9);
		g.addEdge('y', 'z', 2);
		g.addEdge('z', 's', 7);
		g.addEdge('z', 'x', 6);
		g.addEdge('t', 'y', 2);
		g.addEdge('t', 'x', 1);
		g.addEdge('x', 'z', 4);
		vector<int> dist;
		vector<size_t> parentPath;
		g.Dijkstra('s', dist, parentPath);
		g.PrinrtShotPath('s', dist, parentPath);
	}
	void TestGraphBellmanFord()
	{
		/*const char* str = "syztx";
		graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.addEdge('s', 't', 6);
		g.addEdge('s', 'y', 7);
		g.addEdge('y', 'z', 9);
		g.addEdge('y', 'x', -3);
		g.addEdge('z', 's', 2);
		g.addEdge('z', 'x', 7);
		g.addEdge('t', 'x', 5);
		g.addEdge('t', 'y', 8);
		g.addEdge('t', 'z', -4);
		g.addEdge('x', 't', -2);
		vector<int> dist;
		vector<size_t> parentPath;
		if (g.BellmanFord('s', dist, parentPath))
		{
			g.PrinrtShotPath('s', dist, parentPath);
		}
		else
		{
			cout << "存在负权回路" << endl;
		}*/
		// 微调图结构，带有负权回路的测试
		const char* str = "syztx";
		graph<char, int, INT_MAX, true> g(str, strlen(str));
		g.addEdge('s', 't', 6);
		g.addEdge('s', 'y', 7);
		g.addEdge('y', 'x', -3);
		g.addEdge('y', 'z', 9);
		g.addEdge('y', 'x', -3);
		g.addEdge('y', 's', 1); // 新增
		g.addEdge('z', 's', 2);
		g.addEdge('z', 'x', 7);
		g.addEdge('t', 'x', 5);
		g.addEdge('t', 'y', -8); // 更改
		g.addEdge('t', 'z', -4);
		g.addEdge('x', 't', -2);
		vector<int> dist;
		vector<size_t> parentPath;
		if (g.BellmanFord('s', dist, parentPath))
		{
		 g.PrinrtShotPath('s', dist, parentPath);
		}
		else
		{
		 cout << "存在负权回路" << endl;
		}
	}
}




//用邻接表去存储图
namespace link_table
{
	template<class W>
	struct Edge
	{
		int _dst;
		W _w;
		Edge<W>* _next;
		Edge(int dst,const W& w):_dst(dst),_w(w),_next(nullptr)
		{}
	};
	//       vertex   weight
	template<class V, class W=int, bool Direction=false>
	class graph
	{
		typedef Edge<W> Edge;
	public:
		graph(const V* a, size_t n):_vertexs(n),_tables(n,nullptr)
		{
			for (int i = 0; i < n; i++)
			{
				_vertexs[i] = a[i];
				_indexMap[a[i]] = i;
			}
		}
		void addEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = getVertexIndex(src);
			size_t dsti = getVertexIndex(dst);

			Edge* e = new Edge(dsti, w);
			e->_next = _tables[srci];
			_tables[srci] = e;


			if (Direction == false)
			{
				Edge* e = new Edge(srci, w);
				e->_next = _tables[dsti];
				_tables[dsti] = e;
			}
		}

		void print()
		{
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				cout << "[" << i << "] ->" << _vertexs[i] << endl;
			}
			cout << endl;

			for (size_t i = 0; i < _tables.size(); i++)
			{
				cout << _vertexs[i] << "[" << i << "] ";
				Edge* cur = _tables[i];
				while (cur)
				{
					cout << "->" << _vertexs[cur->_dst] << "[" << cur->_dst << "]" << cur->_w;
					cur = cur->_next;
				}
				cout << endl;
			}
		}

	private:
		int getVertexIndex(const V& v)
		{
			auto ret = _indexMap.find(v);
			if (ret == _indexMap.end())
				assert(false);
			else
				return ret->second;
		}

	private:
		vector<V> _vertexs;   //下标映射顶点
		map<V, int> _indexMap;//顶点映射下标 
		vector<Edge*> _tables;
	};

}